﻿#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
//
////水果成篮
////https://leetcode.cn/problems/fruit-into-baskets/
//int ret;
//
//class Solution
//{
//public:
//    int totalFruit(vector<int>& f)
//    {
//        unordered_map<int, int> m1;
//        int left = 0;
//        int right = 0;
//        while (right < f.size())
//        {
//            m1[f[right]]++;
//            while (m1.size() > 2)
//            {
//                m1[f[left]]--;            
//                if (m1[f[left]] == 0)
//                {
//                    m1.erase(f[left]);
//                }
//                left++;
//            }
//            ret = max(ret, right - left + 1);
//            right++;
//        }
//        return ret;
//     }
//};


//数组模拟哈希表
//int ret;
//int kinds;
//
//class Solution
//{
//public:
//    int totalFruit(vector<int>& f)
//    {
//        int hash[100001] = { 0 };
//
//        int left = 0;
//        int right = 0;
//        while (right < f.size())
//        {
//            if (hash[f[right]] == 0) kinds++;
//
//            hash[f[right]]++;
//            while (kinds > 2)
//            {
//                hash[f[left]]--;            
//                if (hash[f[left]] == 0)
//                {
//                    kinds--;
//                }
//                left++;
//            }
//            ret = max(ret, right - left + 1);
//            right++;
//        }
//        return ret;
//     }
//};
//
//
//
//int main()
//{
//    //vector<int> v1 = { 3,3,3,1,2,1,1,2,3,3,4 };
//    vector<int> v2 = { 1,2,3,2,2 };
//    Solution s1;
//    cout << s1.totalFruit(v2) << endl;
//   
//    //cout << "hello world" << endl;
//	return 0;
//}


//找到字符串中所有字⺟异位词
//https://leetcode.cn/problems/find-all-anagrams-in-a-string/
//class Solution
//{
//public:
//    vector<int> findAnagrams(string s, string p)
//    {
//        int m = p.size();
//        int count = 0;
//        int left = 0, right = 0;
//
//        vector<int> ret;
//        int hash1[26] = { 0 };
//        for (auto& e : p)
//        {
//            hash1[e - 'a']++;
//        }
//
//        int hash2[26] = { 0 };
//        
//        while (right < s.size())
//        {
//            char s1 = s[right];
//            hash2[s1 - 'a']++; //进窗口
//            if (hash2[s1 - 'a'] <= hash1[s1 - 'a']) count++;  //进窗口时，维护count
//            if (right - left + 1 > m)
//            {
//                char s2 = s[left];
//                left++;
//                if (hash2[s2 - 'a'] <= hash1[s2 - 'a'])
//                {
//                    count--;                  
//                }               
//                hash2[s2 - 'a']--;
//            }
//
//            if (count == m)
//            {
//                ret.push_back(left);
//            }
//            right++;
//        }
//
//        return ret;
//    }
//};
//
//int main()
//{
//    string s = "cbaebabacd";
//    string p = "abc";
//
//    vector<int> v1;
//    Solution S;
//    v1 = S.findAnagrams(s, p);
//
//    for (auto& e : v1)
//    {
//        cout << e <<  " ";
//    }
//
//	return 0;
//}


//串联所有单词的子串
//https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
//class Solution
//{
//public:
//    vector<int> findSubstring(string s, vector<string>& words)
//    {
//        vector<int> ret;
//        unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
//        for (auto& s : words) hash1[s]++;
//        int len = words[0].size(), m = words.size();
//        for (int i = 0; i < len; i++) // 执⾏ len 次
//        {
//            unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
//            for (int left = i, right = i, count = 0; right + len <= s.size();
//                right += len)
//            {
//                // 进窗⼝ + 维护 count
//                string in = s.substr(right, len);
//                hash2[in]++;
//                if (hash1[in] && hash2[in] <= hash1[in]) count++;
//                // 判断
//                if (right - left + 1 > len * m)
//                {
//                    // 出窗⼝ + 维护 count
//                    string out = s.substr(left, len);
//                    if (hash1[out] && hash2[out] <= hash1[out]) count--;
//                    hash2[out]--;
//                    left += len;
//                }
//                // 更新结果
//                if (count == m) ret.push_back(left);
//            }
//        }
//        return ret;
//    }
//};


//class Solution
//{
//public:
//    vector<int> findSubstring(string s, vector<string>& words)
//    {
//        vector<int> ret;
//        unordered_map<string, int> m1;
//        for (auto& e : words)
//        {
//            m1[e]++;
//        }
//        int x = words[0].size();
//        int len = words.size();
//        
//        for (int i = 0; i < x; i++)
//        {
//            unordered_map<string, int> m2;
//            int left = i, right = i;
//            int count = 0;
//            while (right + x <= s.size())
//            {
//                string s1 = s.substr(right, x);
//                m2[s1]++;
//                if (m1[s1] && m2[s1] <= m1[s1])
//                {
//                    count++;
//                }
//
//                if (right - left + 1 > len * x)
//                {
//                    string s2 = s.substr(left, x);
//                    left += x;
//                    if (m1[s2] && m2[s2] <= m1[s2])
//                    {
//                        count--;
//                    }
//                    m2[s2]--;
//                }
//
//                if (count == len)
//                {
//                    ret.push_back(left);
//                }
//                right += x;
//            }
//        }
//
//        return  ret;
//    }
//};
//
//int main()
//{
//    Solution S;
//    vector<int> v1;
//    vector<int> va;
//    //用例1
//    //string s1 = "barfoothefoobarman";
//    //vector<string> v2 = { "foo","bar" };
//    //用例2
//    string s2 = "barfoofoobarthefoobarman";
//    vector<string> v3 = { "bar","foo","the" };
//    va = S.findSubstring(s2, v3);
//
//    //for (auto& e : v1)
//    //{
//    //    cout << e << " "; 
//    //}
//
//    for (auto& e : va)
//    {
//        cout << e << " "; 
//    }
//
//    //cout << "hello world";
//
//    return 0;
//}
 
//class A
//{
//public:
//	A(int a)
//		:_a1(a)
//		, _a2(_a1)
//	{}
//		void Print() 
//		{
//			cout << _a1 << " " << _a2 << endl;
//		}
//private:
//	int _a2 = 2;
//	int _a1 = 2;
//};
//int main()
//{
//	A aa(1);
//	aa.Print();
//}
